home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / man / cat.3 / Hash.3 < prev    next >
Text File  |  1995-07-25  |  17KB  |  331 lines

  1.  
  2.  
  3.  
  4.      TTTTccccllll____HHHHaaaasssshhhh((((3333))))                  TTTTccccllll (((( ))))                  TTTTccccllll____HHHHaaaasssshhhh((((3333))))
  5.  
  6.  
  7.  
  8.      _________________________________________________________________
  9.  
  10.      NNNNAAAAMMMMEEEE
  11.           Tcl_InitHashTable, Tcl_DeleteHashTable, Tcl_CreateHashEntry,
  12.           Tcl_DeleteHashEntry, Tcl_FindHashEntry, Tcl_GetHashValue,
  13.           Tcl_SetHashValue, Tcl_GetHashKey, Tcl_FirstHashEntry,
  14.           Tcl_NextHashEntry, Tcl_HashStats - procedures to manage hash
  15.           tables
  16.  
  17.      SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  18.           ####iiiinnnncccclllluuuuddddeeee <<<<ttttccccllll....hhhh>>>>
  19.  
  20.           TTTTccccllll____IIIInnnniiiittttHHHHaaaasssshhhhTTTTaaaabbbblllleeee(_t_a_b_l_e_P_t_r, _k_e_y_T_y_p_e)
  21.  
  22.           TTTTccccllll____DDDDeeeelllleeeetttteeeeHHHHaaaasssshhhhTTTTaaaabbbblllleeee(_t_a_b_l_e_P_t_r)
  23.  
  24.           Tcl_HashEntry *
  25.           TTTTccccllll____CCCCrrrreeeeaaaatttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy(_t_a_b_l_e_P_t_r, _k_e_y, _n_e_w_P_t_r)
  26.  
  27.           TTTTccccllll____DDDDeeeelllleeeetttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy(_e_n_t_r_y_P_t_r)
  28.  
  29.           Tcl_HashEntry *
  30.           TTTTccccllll____FFFFiiiinnnnddddHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy(_t_a_b_l_e_P_t_r, _k_e_y)
  31.  
  32.           ClientData
  33.           TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhVVVVaaaalllluuuueeee(_e_n_t_r_y_P_t_r)
  34.  
  35.           TTTTccccllll____SSSSeeeettttHHHHaaaasssshhhhVVVVaaaalllluuuueeee(_e_n_t_r_y_P_t_r, _v_a_l_u_e)
  36.  
  37.           char *
  38.           TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhKKKKeeeeyyyy(_t_a_b_l_e_P_t_r, _e_n_t_r_y_P_t_r)
  39.  
  40.           Tcl_HashEntry *
  41.           TTTTccccllll____FFFFiiiirrrrssssttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy(_t_a_b_l_e_P_t_r, _s_e_a_r_c_h_P_t_r)
  42.  
  43.           Tcl_HashEntry *
  44.           TTTTccccllll____NNNNeeeexxxxttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy(_s_e_a_r_c_h_P_t_r)
  45.  
  46.           char *
  47.           TTTTccccllll____HHHHaaaasssshhhhSSSSttttaaaattttssss(_t_a_b_l_e_P_t_r)
  48.  
  49.      AAAARRRRGGGGUUUUMMMMEEEENNNNTTTTSSSS
  50.           Tcl_HashTable    *_t_a_b_l_e_P_t_r    (in)      Address of hash
  51.                                                   table structure (for
  52.                                                   all procedures but
  53.                                                   TTTTccccllll____IIIInnnniiiittttHHHHaaaasssshhhhTTTTaaaabbbblllleeee,
  54.                                                   this must have been
  55.                                                   initialized by
  56.                                                   previous call to
  57.                                                   TTTTccccllll____IIIInnnniiiittttHHHHaaaasssshhhhTTTTaaaabbbblllleeee).
  58.  
  59.           int              _k_e_y_T_y_p_e      (in)      Kind of keys to use
  60.  
  61.  
  62.  
  63.      Page 1                                          (printed 7/10/95)
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.      TTTTccccllll____HHHHaaaasssshhhh((((3333))))                  TTTTccccllll (((( ))))                  TTTTccccllll____HHHHaaaasssshhhh((((3333))))
  71.  
  72.  
  73.  
  74.                                                   for new hash table.
  75.                                                   Must be either
  76.                                                   TCL_STRING_KEYS,
  77.                                                   TCL_ONE_WORD_KEYS,
  78.                                                   or an integer value
  79.                                                   greater than 1.
  80.  
  81.           char             *_k_e_y         (in)      Key to use for probe
  82.                                                   into table.  Exact
  83.                                                   form depends on
  84.                                                   _k_e_y_T_y_p_e used to
  85.                                                   create table.
  86.  
  87.           int              *_n_e_w_P_t_r      (out)     The word at *_n_e_w_P_t_r
  88.                                                   is set to 1 if a new
  89.                                                   entry was created
  90.                                                   and 0 if there was
  91.                                                   already an entry for
  92.                                                   _k_e_y.
  93.  
  94.           Tcl_HashEntry    *_e_n_t_r_y_P_t_r    (in)      Pointer to hash
  95.                                                   table entry.
  96.  
  97.           ClientData       _v_a_l_u_e        (in)      New value to assign
  98.                                                   to hash table entry.
  99.                                                   Need not have type
  100.                                                   ClientData, but must
  101.                                                   fit in same space as
  102.                                                   ClientData.
  103.  
  104.           Tcl_HashSearch   *_s_e_a_r_c_h_P_t_r   (in)      Pointer to record to
  105.                                                   use to keep track of
  106.                                                   progress in
  107.                                                   enumerating all the
  108.                                                   entries in a hash
  109.                                                   table.
  110.      _________________________________________________________________
  111.  
  112.  
  113.      DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  114.           A hash table consists of zero or more entries, each
  115.           consisting of a key and a value.  Given the key for an
  116.           entry, the hashing routines can very quickly locate the
  117.           entry, and hence its value.  There may be at most one entry
  118.           in a hash table with a particular key, but many entries may
  119.           have the same value.  Keys can take one of three forms:
  120.           strings, one-word values, or integer arrays.  All of the
  121.           keys in a given table have the same form, which is specified
  122.           when the table is initialized.
  123.  
  124.           The value of a hash table entry can be anything that fits in
  125.           the same space as a ``char *'' pointer.  Values for hash
  126.  
  127.  
  128.  
  129.      Page 2                                          (printed 7/10/95)
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.      TTTTccccllll____HHHHaaaasssshhhh((((3333))))                  TTTTccccllll (((( ))))                  TTTTccccllll____HHHHaaaasssshhhh((((3333))))
  137.  
  138.  
  139.  
  140.           table entries are managed entirely by clients, not by the
  141.           hash module itself.  Typically each entry's value is a
  142.           pointer to a data structure managed by client code.
  143.  
  144.           Hash tables grow gracefully as the number of entries
  145.           increases, so that there are always less than three entries
  146.           per hash bucket, on average.  This allows for fast lookups
  147.           regardless of the number of entries in a table.
  148.  
  149.           TTTTccccllll____IIIInnnniiiittttHHHHaaaasssshhhhTTTTaaaabbbblllleeee initializes a structure that describes a
  150.           new hash table.  The space for the structure is provided by
  151.           the caller, not by the hash module.  The value of _k_e_y_T_y_p_e
  152.           indicates what kinds of keys will be used for all entries in
  153.           the table.  _K_e_y_T_y_p_e must have one of the following values:
  154.  
  155.           TTTTCCCCLLLL____SSSSTTTTRRRRIIIINNNNGGGG____KKKKEEEEYYYYSSSS          Keys are null-terminated ASCII
  156.                                    strings.  They are passed to
  157.                                    hashing routines using the address
  158.                                    of the first character of the
  159.                                    string.
  160.  
  161.           TTTTCCCCLLLL____OOOONNNNEEEE____WWWWOOOORRRRDDDD____KKKKEEEEYYYYSSSS        Keys are single-word values;  they
  162.                                    are passed to hashing routines and
  163.                                    stored in hash table entries as
  164.                                    ``char *'' values.  The pointer
  165.                                    value is the key;  it need not (and
  166.                                    usually doesn't) actually point to
  167.                                    a string.
  168.  
  169.           _o_t_h_e_r                    If _k_e_y_T_y_p_e is not TCL_STRING_KEYS
  170.                                    or TCL_ONE_WORD_KEYS, then it must
  171.                                    be an integer value greater than 1.
  172.                                    In this case the keys will be
  173.                                    arrays of ``int'' values, where
  174.                                    _k_e_y_T_y_p_e gives the number of ints in
  175.                                    each key.  This allows structures
  176.                                    to be used as keys.  All keys must
  177.                                    have the same size.  Array keys are
  178.                                    passed into hashing functions using
  179.                                    the address of the first int in the
  180.                                    array.
  181.  
  182.           TTTTccccllll____DDDDeeeelllleeeetttteeeeHHHHaaaasssshhhhTTTTaaaabbbblllleeee deletes all of the entries in a hash
  183.           table and frees up the memory associated with the table's
  184.           bucket array and entries.  It does not free the actual table
  185.           structure (pointed to by _t_a_b_l_e_P_t_r), since that memory is
  186.           assumed to be managed by the client.  TTTTccccllll____DDDDeeeelllleeeetttteeeeHHHHaaaasssshhhhTTTTaaaabbbblllleeee
  187.           also does not free or otherwise manipulate the values of the
  188.           hash table entries.  If the entry values point to
  189.           dynamically-allocated memory, then it is the client's
  190.           responsibility to free these structures before deleting the
  191.           table.
  192.  
  193.  
  194.  
  195.      Page 3                                          (printed 7/10/95)
  196.  
  197.  
  198.  
  199.  
  200.  
  201.  
  202.      TTTTccccllll____HHHHaaaasssshhhh((((3333))))                  TTTTccccllll (((( ))))                  TTTTccccllll____HHHHaaaasssshhhh((((3333))))
  203.  
  204.  
  205.  
  206.           TTTTccccllll____CCCCrrrreeeeaaaatttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy locates the entry corresponding to a
  207.           particular key, creating a new entry in the table if there
  208.           wasn't already one with the given key.  If an entry already
  209.           existed with the given key then *_n_e_w_P_t_r is set to zero.  If
  210.           a new entry was created, then *_n_e_w_P_t_r is set to a non-zero
  211.           value and the value of the new entry will be set to zero.
  212.           The return value from TTTTccccllll____CCCCrrrreeeeaaaatttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy is a pointer to
  213.           the entry, which may be used to retrieve and modify the
  214.           entry's value or to delete the entry from the table.
  215.  
  216.           TTTTccccllll____DDDDeeeelllleeeetttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy will remove an existing entry from a
  217.           table.  The memory associated with the entry itself will be
  218.           freed, but the client is responsible for any cleanup
  219.           associated with the entry's value, such as freeing a
  220.           structure that it points to.
  221.  
  222.           TTTTccccllll____FFFFiiiinnnnddddHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy is similar to TTTTccccllll____CCCCrrrreeeeaaaatttteeeeHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy except
  223.           that it doesn't create a new entry if the key doesn't exist;
  224.           instead, it returns NULL as result.
  225.  
  226.           TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhVVVVaaaalllluuuueeee and TTTTccccllll____SSSSeeeettttHHHHaaaasssshhhhVVVVaaaalllluuuueeee are used to read and
  227.           write an entry's value, respectively.  Values are stored and
  228.           retrieved as type ``ClientData'', which is large enough to
  229.           hold a pointer value.  On almost all machines this is large
  230.           enough to hold an integer value too.
  231.  
  232.           TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhKKKKeeeeyyyy returns the key for a given hash table entry,
  233.           either as a pointer to a string, a one-word (``char *'')
  234.           key, or as a pointer to the first word of an array of
  235.           integers, depending on the _k_e_y_T_y_p_e used to create a hash
  236.           table.  In all cases TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhKKKKeeeeyyyy returns a result with
  237.           type ``char *''.  When the key is a string or array, the
  238.           result of TTTTccccllll____GGGGeeeettttHHHHaaaasssshhhhKKKKeeeeyyyy points to information in the table
  239.           entry;  this information will remain valid until the entry
  240.           is deleted or its table is deleted.
  241.  
  242.           TTTTccccllll____FFFFiiiirrrrssssttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy and TTTTccccllll____NNNNeeeexxxxttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy may be used to scan
  243.           all of the entries in a hash table.  A structure of type
  244.           ``Tcl_HashSearch'', provided by the client, is used to keep
  245.           track of progress through the table.  TTTTccccllll____FFFFiiiirrrrssssttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy
  246.           initializes the search record and returns the first entry in
  247.           the table (or NULL if the table is empty).  Each susequent
  248.           call to TTTTccccllll____NNNNeeeexxxxttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy returns the next entry in the
  249.           table or NULL if the end of the table has been reached.  A
  250.           call to TTTTccccllll____FFFFiiiirrrrssssttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy followed by calls to
  251.           TTTTccccllll____NNNNeeeexxxxttttHHHHaaaasssshhhhEEEEnnnnttttrrrryyyy will return each of the entries in the
  252.           table exactly once, in an arbitrary order.  It is
  253.           unadvisable to modify the structure of the table, e.g.  by
  254.           creating or deleting entries, while the search is in
  255.           progress.
  256.  
  257.           TTTTccccllll____HHHHaaaasssshhhhSSSSttttaaaattttssss returns a dynamically-allocated string with
  258.  
  259.  
  260.  
  261.      Page 4                                          (printed 7/10/95)
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.      TTTTccccllll____HHHHaaaasssshhhh((((3333))))                  TTTTccccllll (((( ))))                  TTTTccccllll____HHHHaaaasssshhhh((((3333))))
  269.  
  270.  
  271.  
  272.           overall information about a hash table, such as the number
  273.           of entries it contains, the number of buckets in its hash
  274.           array, and the utilization of the buckets.  It is the
  275.           caller's responsibility to free the result string by passing
  276.           it to ffffrrrreeeeeeee.
  277.  
  278.           The header file ttttccccllll....hhhh defines the actual data structures
  279.           used to implement hash tables.  This is necessary so that
  280.           clients can allocate Tcl_HashTable structures and so that
  281.           macros can be used to read and write the values of entries.
  282.           However, users of the hashing routines should never refer
  283.           directly to any of the fields of any of the hash-related
  284.           data structures; use the procedures and macros defined here.
  285.  
  286.  
  287.      KKKKEEEEYYYYWWWWOOOORRRRDDDDSSSS
  288.           hash table, key, lookup, search, value
  289.  
  290.  
  291.  
  292.  
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.  
  305.  
  306.  
  307.  
  308.  
  309.  
  310.  
  311.  
  312.  
  313.  
  314.  
  315.  
  316.  
  317.  
  318.  
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.      Page 5                                          (printed 7/10/95)
  328.  
  329.  
  330.  
  331.